/*jshint esversion: 9 */

/**
 * 凸包算法的js实现
 * origin https://www.geeksforgeeks.org/convex-hull-set-1-jarviss-algorithm-or-wrapping/
 * @param points [[1,2],[2,4]]
 */
export function getConvexHull(points){
    if(points.length==0) return [];
    if(points.length<=3) return points;
    //去除重复点位
    const hasPoint = [];
    points.forEach((item,index)=>{
        let string = item.toString();
        if(hasPoint.includes(string)){  //如果已经有了则删除
            points.splice(index,1);
        }else{
            hasPoint.push(string);
        }
    });
    class Point{
        constructor(x, y)
        {
            this.x = x;
            this.y = y;
        }
    }
    // To find orientation of ordered triplet (p, q, r).
    // The function returns following values
    // 0 --> p, q and r are collinear
    // 1 --> Clockwise
    // 2 --> Counterclockwise
    function orientation(p, q, r){
        let val = (q.y - p.y) * (r.x - q.x) -
                    (q.x - p.x) * (r.y - q.y);
        if (val == 0) return 0;  // collinear
        return (val > 0)? 1: 2; // clock or counterclock wise
    }
    // Prints convex hull of a set of n points.
    function convexHull(points, n){
        // There must be at least 3 points
        if (n < 3) return;
        // Initialize Result
        let hull = [];
        // Find the leftmost point
        let l = 0;
        for (let i = 1; i < n; i++)
            if (points[i].x < points[l].x)
                l = i;
        // Start from leftmost point, keep moving
        // counterclockwise until reach the start point
        // again. This loop runs O(h) times where h is
        // number of points in result or output.
        let p = l, q;
        do{
            // Add current point to result
            hull.push(points[p]);
            // Search for a point 'q' such that
            // orientation(p, q, x) is counterclockwise
            // for all points 'x'. The idea is to keep
            // track of last visited most counterclock-
            // wise point in q. If any point 'i' is more
            // counterclock-wise than q, then update q.
            q = (p + 1) % n;
            for (let i = 0; i < n; i++)
            {
            // If i is more counterclockwise than
            // current q, then update q
            if (orientation(points[p], points[i], points[q])
                                                == 2)
                q = i;
            }
            // Now q is the most counterclockwise with
            // respect to p. Set p as q for next iteration,
            // so that q is added to result 'hull'
            p = q;
        } while (p != l);  // While we don't come to first
                        // point
        // Print Result
        // for (let temp of hull.values())
        //     document.write("(" + temp.x + ", " +
        //                         temp.y + ")<br>");
        return hull;
    }
    /* Driver program to test above function */
    let points_ = [];
    points.forEach(item=>{
        points_.push(new Point(item[0],item[1]));
    });
    
    let n = points_.length;
    return convexHull(points_, n).map(item=>[item.x,item.y]);
}